//分隔链表
/*给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* _head = new ListNode(-1, head);
        ListNode* cur = _head;
        bool floag = false;
        ListNode* last;
        // int count = 0;
        while (cur->next) {
           // cout << cur->next->val << " ";
            if (floag == false && cur->next->val >= x) {
                floag = true;
                last = cur;
            } else if (floag && cur->next->val < x) {
                // count++;
                // cout << count << " ";
                ListNode* temp = cur->next;
                ListNode* old_next = temp->next;
                ListNode* new_next = last->next;
                cur->next = old_next;
                temp->next = new_next;
                last->next = temp;
                last = last->next;
                // cout << last->val << " ";
            } else if (cur->next)
                cur = cur->next;
        }
        return _head->next;
    }
};


//完全二叉树的节点个数
/*给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
    int count = 0;

public:
    int countNodes(TreeNode* root) {
        dfs(root);
        return count;
    }
    void dfs(TreeNode* root) {
        if (root == nullptr)
            return;
        else
            count++;
        dfs(root->left);
        dfs(root->right);
    }
};